package Test;

public class 最长公共子序列 {
    public static int longestCommonSubsequence(String s1, String s2) {
        int[][] dp=new int[s1.length()+1][s2.length()+1];
        for (int i=1;i<s1.length()+1;i++){
            for (int j=1;j<s2.length()+1;j++){
                if(s1.charAt(i-1)==s2.charAt(j-1)){
                    dp[i][j]=1+dp[i-1][j-1];
                }else {
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[s1.length()][s2.length()];
    }

    public static void main(String[] args) {
        String s1="abcde";
        String s2="abc";
        System.out.println(longestCommonSubsequence(s1,s2));
    }
}
